Матч 255, К-ый элемент (KthElement)

Дивизион 2, Уровень 3

Обозначим через F(n) функцию, которая вычисляет количество единиц в бинарном представлении числа n. Например, F(279) = 5, так как 279 = (100010111)₂. Последовательность Х строится следующим образом: X₀ = 0, X_i = A * F(X_i-1) + B. По заданным A, B, K найти K – ый элемент последовательности Х.

Класс: KthElement

Метод: int find(int A, int B, int K)

Ограничения: 0 £ A, B £ 10⁶, 1 £ K £ 10⁹.

Вход. Три числа A, B, K.

Выход. Значение X_k.

Пример входа

A	B	K
0	12	5
1	7	15
15	21	500000001

Пример выхода

12

9

51

РЕШЕНИЕ

математика

F(X_i) принимают конечное множество значений. Поэтому начиная с некоторого индекса pos, значения F(X_i) начнут образовывать повторяющийся цикл. Предположим, что индекс len минимальный, для которого X_pos = X_len. Таким образом, длина цикла (повторяющейся части) равна len – pos. Все значения F(X_i), где i < len, будем хранить в векторе seq. То есть seq[i] = F(X_i) для i < len. Если искомый номер последовательности k < len, то достаточно вывести значение seq[k]. Иначе ищем минимальный индекс j последовательности X, для которого X_j = X_k. Он равен j = pos + (k – pos) % (len – pos). Выводим seq[j] = X_j.

ПРИМЕР

Рассмотрим третий тест. Последовательность X_i имеет вид: 0, 21, 66, 51, 81, 66, 51, 81, 66, ... . Циклическая часть последовательности состоит из трех чисел и имеет вид 66, 51, 81. Для этой последовательности pos = 2 (нумерация индексов последовательности и вектора начинается с нуля), len = 5 (X₂ = X₅). Вычисляем минимальный индекс j последовательности X, для которого X_j = X_k: j = pos + (k – pos) % (len – pos) = 2 + (500000001 – 2) % (5 – 2) = 2 + 1 = 3. Таким образом X_500000001 = X₃ = 51.

Функция int f(int x) вычисляет F(x).

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

class KthElement

{

public:

int f(int x)

{

int res = 0;

while(x > 0)

{

x = x & (x - 1);

res++;

}

return res;

}

int find(int a, int b, int k)

{

vector<int> seq;

int x = 0, pos, len;

while(std::find(seq.begin(),seq.end(),x) == seq.end())

{

seq.push_back(x);

x = a * f(x) + b;

}

pos = (int)(std::find(seq.begin(),seq.end(),x) - seq.begin());

len = seq.size();

if (k < len) return seq[k];

return seq[pos + (k - pos) % (len - pos)];

}

};